/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRKB30
␈↓ α∧␈↓␈↓ u1


␈↓ α∧␈↓CS206␈↓ ¬TFINAL EXAMINATION␈↓ 
lFALL 1983 

␈↓ α∧␈↓␈↓ αTThis␈α
examination␈α
is␈α
open␈α∞book␈α
and␈α
notes.␈α
 Write␈α∞LISP␈α
functions␈α
or␈α
predicates␈α∞and␈α
make
␈↓ α∧␈↓proofs␈αas␈αfollows␈α
except␈αwhere␈αsomething␈α
else␈αis␈αrequested.␈α
 Either␈αnotation␈αmay␈α
be␈αused.␈α Be␈α
sure
␈↓ α∧␈↓to␈α
indicate␈α
in␈α
an␈α
emphatic␈α
way␈α
the␈α
logical␈αsentences␈α
indicating␈α
what␈α
is␈α
to␈α
be␈α
proved␈α
and␈α
the␈α␈↓	F␈↓'s␈α
of
␈↓ α∧␈↓any␈αinductions␈α
that␈αneed␈α
to␈αbe␈αmade.␈α
 You␈αmay␈α
assume␈αthat␈αyour␈α
functions␈αare␈α
total␈αbut␈α
will␈αbe
␈↓ α∧␈↓suitably penalized if they aren't.

␈↓ α∧␈↓␈↓ αTThe␈αexamination␈αis␈αa␈α"take␈αhome"␈αand␈αis␈αdue␈αat␈α1983␈αDecember␈α13␈αTuesday␈α7pm␈αin␈αRoom
␈↓ α∧␈↓353␈α
Margaret␈α
Jacks␈α
Hall.␈α
 It␈α
may␈α
also␈α
be␈α
left␈α
earlier␈α
with␈α
Diana␈α
Hall␈α
in␈α
Room␈α
358␈αMargaret␈α
Jacks
␈↓ α∧␈↓Hall.

␈↓ α∧␈↓1.␈α
We␈α
will␈α
say␈α
that␈αa␈α
list␈α
␈↓↓u␈↓␈α
is␈α
"intermittently␈α
contained"␈αin␈α
a␈α
list␈α
␈↓↓v␈↓␈α
if␈α
the␈αelements␈α
of␈α
␈↓↓u␈↓␈α
occur␈α
in␈α␈↓↓v␈↓␈α
in
␈↓ α∧␈↓the␈α
same␈α
order␈α
as␈α
in␈α∞␈↓↓u␈↓␈α
but␈α
possibly␈α
separated␈α
by␈α
other␈α∞elements␈α
of␈α
␈↓↓v.␈↓␈α
We␈α
write␈α
␈↓↓u ≤≤ v␈↓␈α∞for␈α
this
␈↓ α∧␈↓relation.  Thus we have (A C E) ≤≤ (X A B C A F D E G).

␈↓ α∧␈↓␈↓ αTa. Write a recursive definition of ␈↓↓u ≤≤ v␈↓.

␈↓ α∧␈↓Prove

␈↓ α∧␈↓␈↓ αTb. that your ␈↓↓u ≤≤ v␈↓ is total

␈↓ α∧␈↓␈↓ αTc. ␈↓↓∀u:u << u␈↓.

␈↓ α∧␈↓␈↓ αTd. ␈↓↓∀u v w:(u ≤≤ v ∧ v ≤≤ w ⊃ u ≤≤ w)␈↓.

␈↓ α∧␈↓2. ␈↓↓iscompact x␈↓, where ␈↓↓x␈↓ is a list structure, is true if all EQUAL substructures in ␈↓↓x␈↓ are EQ.

␈↓ α∧␈↓␈↓↓compactify x␈↓ makes a copy of ␈↓↓x␈↓ that satisfies ␈↓↓iscompact␈↓.

␈↓ α∧␈↓What␈α
problem␈α
arises␈α
in␈α
trying␈α
to␈α
prove␈α
the␈α
properties␈α
of␈α
␈↓↓iscompact␈↓␈α
by␈α
the␈α
methods␈α
discussed␈αin
␈↓ α∧␈↓CS206?

␈↓ α∧␈↓3.␈α∂␈↓↓partitions␈α∂n␈↓␈α∂is␈α∂a␈α∂list␈α∂of␈α∂the␈α⊂partitions␈α∂of␈α∂the␈α∂integer␈α∂␈↓↓n␈↓␈α∂into␈α∂sums␈α∂of␈α∂smaller␈α⊂integers.␈α∂ Thus
␈↓ α∧␈↓␈↓↓partitions 1 = ((1)),␈α∞partitions 2 = ((2) (1 1)),␈α∞partitions␈α∞3␈α∞=␈α∞((3) (2 1) (1 1 1)),␈α∂and␈α∞partitions 4 =
␈↓ α∧␈↓↓((4) (3 1) (2 2) (2 1 1) (1 1 1 1))␈↓.

␈↓ α∧␈↓4 Pattern matching and substitution

␈↓ α∧␈↓␈↓ αT␈↓↓sublis[pattern,␈αalist]␈↓␈αis␈αthe␈αresult␈αof␈αmaking␈αthe␈αsubstitutions␈αdescribed␈αin␈α␈↓↓alist␈↓␈αin␈α␈↓↓pattern.␈↓
␈↓ α∧␈↓Thus

␈↓ α∧␈↓␈↓↓sublis␈↓[(PLUS␈α
X␈α
(TIMES␈α
X␈α
Y)␈α
A),␈α
((X.A)␈α
(Y.(PLUS␈α
X␈α
Y)))]␈α
=␈α
(PLUS␈α
A␈α
(TIMES␈α
A␈α∞(PLUS␈α
X
␈↓ α∧␈↓Y)) A)

␈↓ α∧␈↓␈↓↓match[pattern,expression,alist]␈↓␈α∪attempts␈α∪to␈α∪match␈α∪␈↓↓pattern␈↓␈α∪against␈α∪␈↓↓expression␈↓␈α∪to␈α∪produce␈α∪and
␈↓ α∧␈↓extension␈α⊂of␈α⊂␈↓↓alist␈↓␈α⊂such␈α⊃that␈α⊂substituting␈α⊂in␈α⊂the␈α⊂pattern␈α⊃according␈α⊂to␈α⊂the␈α⊂result␈α⊂will␈α⊃give␈α⊂back
␈↓ α∧␈↓␈↓↓expression␈↓.␈α If␈α
the␈αmatch␈α
is␈αunsuccessful,␈αthe␈α
value␈αis␈α
the␈αatom␈αNO.␈α
 It␈αis␈α
assumed␈αthat␈αa␈α
predicate
␈↓ α∧␈↓␈↓↓isvar␈↓␈α∞applicable␈α∞to␈α∂atoms␈α∞is␈α∞available␈α∞that␈α∂distinguishes␈α∞variables␈α∞from␈α∞other␈α∂atoms.␈α∞ Assuming
␈↓ α∧␈↓that ␈↓↓X␈↓ and ␈↓↓Y␈↓ are variables, we have
␈↓ α∧␈↓␈↓ u2


␈↓ α∧␈↓␈↓↓match␈↓[(PLUS X Y), (PLUS A (TIMES B C)),NIL] = ((X.A) (Y TIMES B C)),

␈↓ α∧␈↓and

␈↓ α∧␈↓␈↓↓match␈↓[(PLUS X Y), (PLUS A (TIMES B C)),((X.B))] = NO.

␈↓ α∧␈↓a. Write recursive programs for ␈↓↓sublis␈↓ and ␈↓↓match.␈↓

␈↓ α∧␈↓b. Write accurately the sentence that expresses the fact that ␈↓↓sublis␈↓ and ␈↓↓match␈↓ are partial inverses.

␈↓ α∧␈↓c. Prove the sentence of part b.

␈↓ α∧␈↓5.␈α∂Let␈α⊂␈↓↓e␈↓␈α∂be␈α∂a␈α⊂LISP␈α∂expression␈α⊂formed␈α∂from␈α∂numbers␈α⊂and␈α∂atoms␈α∂using␈α⊂PLUS␈α∂and␈α⊂TIMES␈α∂to
␈↓ α∧␈↓represent␈α∪addition␈α∪and␈α∩multiplication.␈α∪ ␈↓↓polyprint e␈↓␈α∪is␈α∩a␈α∪list␈α∪of␈α∩the␈α∪characters␈α∪occurring␈α∪in␈α∩a
␈↓ α∧␈↓printout of ␈↓↓e␈↓ in algebraic notation containing no unnecessary parentheses.  Thus

␈↓ α∧␈↓␈↓ αT␈↓↓polyprint␈↓ (TIMES (PLUS X (TIMES U V W)) X Z) = (LP X PLUS U V W RP X Z)

␈↓ α∧␈↓which corresponds to the algebraic expression (X + UVW)XZ

␈↓ α∧␈↓6. Derived functions

␈↓ α∧␈↓␈↓ αTCertain␈α⊃properties␈α∩of␈α⊃LISP␈α∩functions␈α⊃are␈α∩expressed␈α⊃by␈α∩related␈α⊃functions␈α∩called␈α⊃derived
␈↓ α∧␈↓functions.  For example, consider

␈↓ α∧␈↓␈↓↓flatten x ← ␈↓αif␈↓↓ ␈↓αa␈↓↓t x ␈↓αthen␈↓↓ <x> ␈↓αelse␈↓↓ flatten ␈↓αa␈↓↓ x * flatten ␈↓αd␈↓↓ x␈↓.

␈↓ α∧␈↓Let␈α␈↓↓cflatten␈αx␈↓␈αbe␈αthe␈αnumber␈αof␈αtimes␈αLISP␈αexecutes␈α␈↓↓cons␈↓␈αin␈αevaluating␈α␈↓↓flatten␈αx␈↓.␈α Clearly␈α
␈↓↓cflatten␈↓
␈↓ α∧␈↓satisfies the recursions

␈↓ α∧␈↓␈↓↓cflatten x ← ␈↓αif␈↓↓ ␈↓αa␈↓↓t x ␈↓αthen␈↓↓ 1

␈↓ α∧␈↓↓␈↓ αT␈↓αelse␈↓↓ cflatten ␈↓αa␈↓↓ x + cflatten ␈↓αd␈↓↓ x + cappend[flatten ␈↓αa␈↓↓ x, flatten ␈↓αd␈↓↓ x]␈↓,

␈↓ α∧␈↓↓where cappend[u,v] is the number of conses done in computing u*v␈↓ and satisfies

␈↓ α∧␈↓␈↓↓cappend[u,v] ← ␈↓αif␈↓↓ ␈↓αn␈↓↓ u then 0 ␈↓αelse␈↓↓ 1 + cappend[␈↓αd␈↓↓ u, v]␈↓.

␈↓ α∧␈↓␈↓ αTOur other way of flattening a list involves

␈↓ α∧␈↓␈↓↓flat[x,u] ← ␈↓αif␈↓↓ ␈↓αa␈↓↓t x ␈↓αthen␈↓↓ x.u ␈↓αelse␈↓↓ flat[␈↓αa␈↓↓ x, flat[␈↓αd␈↓↓ x, u]]␈↓.

␈↓ α∧␈↓Let ␈↓↓cflat[x,u]␈↓ be the number of ␈↓↓cons␈↓es done in computing ␈↓↓flat[x,u]␈↓.

␈↓ α∧␈↓␈↓ αTa. Write the recursion for ␈↓↓cflat[x,u]␈↓.

␈↓ α∧␈↓␈↓ αTb. Prove ␈↓↓∀x u: 2cflat[x,u] ≤ cflatten x␈↓.